package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      水平反转二进制矩阵，然后翻折矩阵，将元素为0改为1,1改为0
 *
 * 2. 算法分析
 *      1.  暴力法   时间复杂度为O(n^2)
 *
 *      2.
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q025_翻折图片 {
    // 暴力法
    public int[][] flipAndInvertImage1(int[][] A) {
        int row = A.length;
        int col = A[0].length;
        // 水平翻折
        for(int i = 0; i < row; i++) { // 扫描行
            // 翻折第i行
            for(int j = 0; j < col / 2; j++) {
                int temp = A[i][j];
                A[i][j] = A[i][col - j - 1];
                A[i][col - j - 1] = temp;
            }
        }
        // 反转
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                A[i][j] = (A[i][j] == 0) ? 1 : 0;
            }
        }
        return A;
    }

    // 优化 虽然代码边长了，但是时间和空间都提升了不少

    /**
     * 优化思路：
     *      // 暴力法肯定可以实现，但是效率不高，因为我们并没有注意上述两种变化之间存在的关系
     *     // 对于反转而言就是将二进制矩阵的每一行进行逆序，而所谓的翻折就是将二进制矩阵中的
     *     // 0,1变化而已，但是在此过程中会有这样的情况出现：假设当前反转第i行中的第j1和j2元
     *     // 素,并且两个元素之间不相同，即一个为0一个为1，假设j1为0，j2为1，反转之后j1为1，
     *     // j2为0，然后通过翻折操作，我们发现j1为0，j2为1，与没有进行任何操作之前是一样的
     *     // 所以我们只需要考虑两个位置向的元素相同的情况，而不需要暴力操作，这样时间就节省下来了
     * @param A
     * @return
     */
    public int[][] flipAndInvertImage2(int[][] A) {
        int row = A.length;
        int col = A[0].length;
        if(col % 2 == 0) {
            for(int i = 0; i < row; i++) {
                for(int j = 0; j < col / 2; j++) {
                    if(A[i][j] == A[i][col - j - 1]) {
                        A[i][j] = (A[i][j] == 0) ? 1 : 0;
                        A[i][col - j - 1] = (A[i][col - j - 1] == 0) ? 1 : 0;
                    }
                }
            }
        } else {
            for(int i = 0; i < row; i++) {
                for(int j = 0; j <= col / 2; j++) {
                    if(j == col / 2) {
                        A[i][j] = (A[i][j] == 0) ? 1 : 0;
                    } else {
                        if(A[i][j] == A[i][col - j - 1]) {
                            A[i][j] = (A[i][j] == 0) ? 1 : 0;
                            A[i][col - j - 1] = (A[i][col - j - 1] == 0) ? 1 : 0;
                        }
                    }
                }
            }
        }
        return A;
    }


    // 优化
    /**
     * 优化思路：
     *   延续上述的思路，但是我们将中间元素的变化直接提出来，单独讨论，简化了代码的编写
     * @param A
     * @return
     */
    public int[][] flipAndInvertImage3(int[][] A) {
        int row = A.length;
        int col = A[0].length;
        // 由于对于奇偶矩阵中间元素的考虑，我们先考虑中间元素，如果为奇数中间元素唯一
        // 如果为偶数中间元素有两个
        if(col % 2 != 0) {
            for(int i = 0; i < row; i++) {
                A[i][col / 2] = (A[i][col / 2] == 0) ? 1 : 0;
            }
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col / 2; j++) {
                if(A[i][j] == A[i][col - j - 1]) {
                    A[i][j] = (A[i][j] == 0) ? 1 : 0;
                    A[i][col - j - 1] = (A[i][col - j - 1] == 0) ? 1 : 0;
                }
            }
        }
        return A;
    }

}
